The present invention relates to a state metric memory, and more particularly to an apparatus which increases processing speed by reconstructing the state metric memory employed in a viterbi decoder for correcting errors created in a digital transmission channel.
The viterbi decoder is an apparatus for decoding data that is encoded in convolutional code by employing a maximum likelihood decoding method with viterbi algorithm. The viterbi decoder compares the code sequence of received data with a predetermined code sequence of the encoder to select the nearest path of the code sequence and decode the code transmitted from the selected path. Among the various methods for decoding a convolutional code, a decoder adopting the viterbi method is used due to its significant decoding benefit in communications systems where the quality of transmission path deteriorates or the transmitted signal levels are severely limited.
As illustrated in FIG. 1, a conventional viterbi decoder comprises an input buffer 100, a branch metric calculator 200, an add compare selector 300, a state metric memory 400, a path trace-back logic circuit 500, a path memory 600, and a main clock generator 700.
Generally, input buffer 100, connected between a receiver (not shown) and a decoder, transmits data received from input terminal IN to branch metric quantity calculator 200 which compares the data from the encoder and the received data to output a neighboring value to them. Add compare selector 300 adds the branch metric quantity calculated in branch metric quantity calculator 200 to the metric quantity of a previous state stored in state metric quantity memory 400, and compares the added metric quantity with the previous metric quantity to output a state metric quantity Sm having a path sequence nearest to the transmitted code sequence. The state metric quantity Sm added in the add compare selector 300 is stored again in state metric memory quantity 400, the selected paths are stored in path memory 600 through path trace-back logic circuit 500. Path trace back logic circuit 500 traces path information stored in path memory 600, and outputs to output terminal OUT data that is nearest to the transmitted data of a transmitter.
At this time, main clock generator 700 receives an input clock signal CLOCK to transmit a main clock signal MAIN CLOCK to each unit.
The add compare selector 300 and state metric quantity memory 400 adopted in the viterbi encoder as described above are depicted in detail in FIG. 2. Adders 310 and 320 constituting the add compare selector 300 add branch metric quantities Bmi, Bm(i+1) transmitted from branch metric quantity calculator 200 and the previous state metric quantities Sm(a) and Sm(b) transmitted from state metric quantity memory device 410 of state metric quantity memory 400 so as to transmit output signals to comparator 330 and selector 340. The comparator 330 receives and compares the signals generated from each adder 310 and 320, and the resultant signals generated after comparison are transmitted to selector 340.
Receiving the compared signals from comparator 330, selector 340 selects a signal having a smaller state metric quantity from among the signals transmitted from adders 310 and 320 to set a new state metric quantity Sm(c) and stores it in state metric quantity memory 400. Memory location designator 420 then transmits an address to state metric quantity memory device 410 to designate a memory location.
To explain the operation of the viterbi decoder, a trellis diagram of decoding a signal encoded in convolutional code of code ratio R=1/2 and constraint length K=3 is shown in FIG. 3, which is repeated according to the variations of decode time point j. As the total number of states of the state metric quantities Sm supplied from branch metric quantity calculator 200 becomes 2.sup.k-1, the total number of states when the constraint length K is 3 as shown in FIG. 3 becomes 4. At this time, if the present time point is j+1, the calculation of each state is represented by the below equations 1 to 4. EQU Sm.sub.(j+1) 0=MIN[Smj0+Bm0,Smj1+Bm1] &lt;equation 1&gt; EQU Sm.sub.(j+1) 1=MIN[Smj2+Bm2,Smj3+Bm3] &lt;equation 2&gt; EQU Sm.sub.(j+1) 2=MIN[Smj0+Bm1,Smj1+Bm0] &lt;equation 3&gt; EQU Sm.sub.(j+1) 3=MIN[Smj2+Bm3,Smj3+Bm2] &lt;equation 4&gt;
As expressed in the above equations 1 to 4, calculating all state metric quantities Sm of current decode time point (j+1) and a double reading of the state metric quantity for decode time point j of former state must be carried out in order to store the state metric quantities in memory device 410. As a result, memory location designator 420 shown in FIG. 2 is required to designate a different location during each period of read-out and write-in of the memory address of state metric quantity memory device 410.
Meanwhile, the decode processing speed which usually depends on the state metric quantity calculating speed takes much more time to read and write each state metric quantity Sm in state memory 400 than the time required for calculating in the add compare selector 300 so that the processing speed is limited. The reason for this is that, in case of add compare selector 300, only the processing in a logic circuit is delayed, but in case of state metric quantity memory 400, the designation of the memory locations for read-out and write-in operation of the add compare selector 300 should be carried out in such a manner as expressed in Equations 1 to 4, resulting in much delay time and requiring access time to write-in and read-out data in the state metric quantity memory device 410. Thus, in order to have high speed access time for high speed data decode processing, the add compare selector 300 and the state metric quantity memory 400 composed of a memory location designator 420 and a state metric quantity memory device 410 are connected to each other in parallel to be used for calculation at the same time. Thus, the veterbi decoder using the above described methods has the disadvantages of high production cost and complex circuitry.